/*
完成
关系S排序
使用的段从65开始，65到80是第一次排序结果，四个blk为一组进行排序
81-96为最终的排序结果，
关系R排序
使用的段从65开始，100到131是第一次排序结果，六个blk为一组进行排序
132到163是最终的排序结果，
*/

#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
#include "extmem.h"
#include "t2.h"

// N1 为要分的组数
#define N1 4
#define N2 6
#define RBlockNum 16
#define SBlockNum 32
// 一个块中元组的数量
#define SizeofBlock 7
// 一个元组占用的字节数
#define Tuplelength 8


// int wf=65;
// int main(int argc, char const *argv[])
// {
//     Buffer buf;
//     if (!initBuffer(520, 64, &buf))
//     {
//         perror("Buffer Initialization Failed!\n");
//         return -1;
//     }
//     // 对R关系进行排序
//     sortBlocks(1,65,N1,RBlockNum,&buf);
//     // 对S关系进行排序
//     sortBlocks(17,100,N2,SBlockNum,&buf);

//     printf("\nbuf IO num:%ld\n",buf.numIO);
//     return 0;

// }

// rf为读入块的开始位置
// wf为写入块的初始位置 因为写入文件的起始位置是要变动的（wf的值会变动），采用传参的方式
// groupSize
void sortBlocks(int rfStart,int wf,int groupSize,int length,Buffer *buf)
{
    int wfStart=wf;//记录头位置，用于第二次读入
    int SecondGroupNum=((length-1)/groupSize)+1;
    sortFirst(buf,rfStart,length,&wf,groupSize);
    int blkNo[SecondGroupNum];
    for (int i = 0; i < SecondGroupNum; i++)
    {
        blkNo[i]=wfStart+i*groupSize;
    }
    
    sortSecond(blkNo,groupSize,SecondGroupNum,length,&wf,buf);
}

// refTime为循环分组次数,groupNum为一组block最大数量,lastBlockNum为该最系最后的块下标
// 以S关系举例，有32个块，6个为一组，第一次分组为5个6块组，一个2块组，refTime=32/6+1=6，blockOfGroup=6
void sortFirst(Buffer *buf,int readOffset,int length,int *wf,int groupSize)
{
    int refTime=((length-1)/groupSize)+1;
    int lastBlock=readOffset+length-1;
    // 四个指针指向四块block
    unsigned char *r[groupSize];
    int p[groupSize];
    int X[groupSize];
    int Y[groupSize];
    int ovflag[groupSize];
    int factgroup=groupSize;
    //每次循环形成一个有序组
    for (int i = 0; i < refTime; i++)
    {
        memset(&ovflag,0,sizeof(int)*groupSize);
        memset(&X,0,sizeof(int)*groupSize);
        memset(&Y,0,sizeof(int)*groupSize);
        memset(&p,0,sizeof(int)*groupSize);
        memset(r,0,sizeof(unsigned char *)*groupSize);
        // 读入组中的每一个块
        for (int k = 0; k < groupSize; k++)
        {
            // 如果已经越界，就别读了
            if (groupSize*i+k+readOffset>lastBlock)
            {
                // 提前宣布该块结束
                factgroup=k;
                for (int t = k; t < groupSize; t++)
                {
                    ovflag[t]=1;
                }
                break;
            }
            r[k] = readBlockFromDisk(groupSize*i+k+readOffset, buf);
            if (r[k]==NULL)
            {
                perror("Reading Block Failed!\n");
                exit(-1);
            }
            // 先将读入的每一个blk进行自身的排序，从小到大
            blkSort(r[k]);
        }
        
        // 写入块
        unsigned char *w1 = getNewBlockInBuffer(buf);
        int wp=0;
        // 从读入块中获取值
        for (int k = 0; k < factgroup; k++)
        {
            getValueByp(&X[k],&Y[k],p[k],r[k]);
            if (p[k]==-1)
            {
                perror("error in first data read\n");
            }
        }
        // 每次排序有N1组，每组有7个元组
        // 有可能一个group没有填满
        for (int k = 0; k < SizeofBlock*factgroup; k++)
        {
            int index=judgeSmall(ovflag,X,factgroup);
            if(writeData(&p[index],&wp,r[index],w1,wf,buf))
            {
                ovflag[index]=1;
            }
            if (!ovflag[index])
            {
                getValueByp(&X[index],&Y[index],p[index],r[index]);
            }
        }

        // 释放内存中的块(r[4])
        for (int k = 0; k < factgroup; k++)
        {
            // 似乎犯了个低级的错误，此处的offset应该是k，写成了i
            freeBlockInBuffer(r[k],buf);
        }
        freeBlockInBuffer(w1,buf);
    }
}

// 进行第二轮排序，四个blk为一组
void sortSecond(int *blkNo,int groupSize,int groupNum,int length,int *wf,Buffer *buf)
{
    int lastBlock=blkNo[0]+length-1;
    // 四个指针指向四块block
    unsigned char *r[groupNum];
    // 每个内存组中的下标偏移
    int p[groupNum];
    // 四组的当前X值
    int X[groupNum];
    // 四组的当前Y值
    int Y[groupNum];
    // 当前硬盘组中的数据是否已经读取完毕
    int ovflag[groupNum];
    // 标记四个硬盘组读到的位置 
    // int blkNo[4]={65,69,73,77};
    // 初始位置，不变动
    int blkBase[groupNum];
    for (int i = 0; i < groupNum; i++)
    {
        blkBase[i]=blkNo[i];
    }
    
    // int blkLength[groupNum];

    memset(&ovflag,0,sizeof(int)*groupNum);
    memset(&X,0,sizeof(int)*groupNum);
    memset(&Y,0,sizeof(int)*groupNum);
    memset(&p,0,sizeof(int)*groupNum);
    memset(r,0,sizeof(unsigned char *)*groupNum);
    // memset(blkLength,0,sizeof(int)*groupNum);

    // 读入内存中每一组的初始化
    for (int k = 0; k < groupNum; k++)
    {
        // 每次读取blkNo加1
        r[k] = readBlockFromDisk(blkNo[k]++, buf);
        if (r[k]==NULL)
        {
            perror("Reading Block Failed!\n");
            exit(-1);
        }
    }
    // 写块的初始化
    unsigned char *w1 = getNewBlockInBuffer(buf);
    int wp=0;
    // 初始化X和Y的数组（先从中取出一组值）
    for (int k = 0; k < groupNum; k++)
    {
        getValueByp(&X[k],&Y[k],p[k],r[k]);
        if (p[k]==-1)
        {
            perror("error in first data read\n");
        }
    }
    // 112=16*7，每组有7个元素，一共有16组
    for (int i = 0; i < length*SizeofBlock; i++)
    {
        // index为被选中的组的下标
        int index=judgeSmall(ovflag,X,groupNum);
        // 如果有一个组已经被写完
    // todo:
    // 1.判断该组是否是最后一个组，如果是，打上ovflag标记
    // 2.如果不是，读入下一个组，并将该组的p置零
        // printf("\nX:%d\n",X[index]);
        if(writeData(&p[index],&wp,r[index],w1,wf,buf))
        {
            freeBlockInBuffer(r[index],buf);
            // 该组已经结束
            if (blkNo[index]-blkBase[index]==groupSize || blkNo[index]>lastBlock)
            {
                ovflag[index]=1;
            }
            else
            {
                r[index]=readBlockFromDisk(blkNo[index]++,buf);
                p[index]=0;
            }
        }
        if (!ovflag[index])
        {
            getValueByp(&X[index],&Y[index],p[index],r[index]);
        }
    }


}

// 返回值代表当前rblk是否读完，读完返回1
// wf为开始的文件写入块号
int writeData(int *rp,int *wp,unsigned char *rblk,unsigned char *w1,int *wf,Buffer *buf)
{
   
    // 将整个元组的数据复制到写出block
    for (int i = 0; i < 8; i++)
    {
        *(w1+*wp)=*(rblk+*rp);
        (*wp)++;
        (*rp)++;
    }
    if (*wp==56)
    {
        // printf("write %d to the disk\n",++wcount);
        //将下一个块的指针存入p=57中，并将当前块的数据写入磁盘块中，清空当前块
        char next[5];
        itoa((*wf)+1,next);
        // printf("\nis here?%s\n",next);
        int t=0;
        while (next[t]!='\0')
        {
            *(w1+*wp)=next[t];
            (*wp)++;
            t++;
        }
        
        
        if (writeBlockToDisk(w1, (*wf)++, buf) != 0)
        {
            perror("Writing Block Failed!\n");
            exit(-1);
        }
        w1 = getNewBlockInBuffer(buf);
        // 重新从0开始写数据，就相当于使用了free
        // api里的free相当于告知buf当前块已不再需要使用
        *wp=0;
    }
    if (*rp>=56)
    {
        return 1;
    }
    return 0;  
}

int judgeSmall(int *ovflag,int *X,int size)
{
    // printf("\nX\n:");
    // for (int i = 0; i < size; i++)
    // {
    //     printf("X[%d]:%d\n",i,X[i]);
    // }
    // printf("\novflag\n:");
    // for (int i = 0; i < size; i++)
    // {
    //     printf("ovflag[%d]:%d\n",i,ovflag[i]);
    // }
    int smallIndex=0;
    while (ovflag[smallIndex])
    {
        smallIndex++;
    }
    
    for (int i = 0; i < size; i++)
    {
        if (X[i]<X[smallIndex]&&ovflag[i]!=1)
        {
            smallIndex=i;
        }
    }
    // printf("\nselected:%d",X[smallIndex]);
    return smallIndex;    
}

char* itoa(int num,char *s)
{
    char *p=s;
    char *head=s;
    char temp;
    int res;
    do
    {
        *p++=(char)(num%10+'0');
        num/=10;
        /* code */
    } while (num>0);
    *p--='\0';
    // 原地换位
    do
    {
        temp=*p;
        *p=*head;
        *head=temp;
        p--;
        head++;
    } while (head<p);
    return s;
}

// 根据block块中的偏移p来获取X和Y值，返回获取后的p值
int getValueByp(int *X,int *Y,int p,unsigned char *blk)
{
    if (p>=56)
    {
        perror("error in getValueByp,cross line");
        exit(-1);
    }
    char strX[5],strY[5];
    for (int i = 0; i < 4; i++)
    {
        strX[i] = *(blk+p);
        p++;
    }
    
    for (int i = 0; i < 4; i++)
    {
        strY[i] = *(blk+p);
        p++;
    }

    *X = atoi(strX);
    *Y = atoi(strY);

}


// 使用冒泡排序，7个元组，需要经过6次冒泡
// 小的元素放在前面
void blkSort(unsigned char *blk)
{
    // 
    for (int i = 0; i < 6; i++)
    {
        char strX[4];
        char strX_aft[4];
        for (int p =0; p < 48-8*i; p+=8)
        {
            memcpy(strX,&blk[p],4);
            memcpy(strX_aft,&blk[p+8],4);
            int X=atoi(strX);
            int X_aft=atoi(strX_aft);
            if (X>X_aft)
            {
                changePlace(blk,p,p+8);
            }
        }
    }
}

// 将blk中p1位置开始的元组和p2位置开始的元组交换位置
void changePlace(unsigned char *blk,int p1,int p2)
{
    char res[8];
    memcpy(res,&blk[p1],8);
    memcpy(&blk[p1],&blk[p2],8);
    memcpy(&blk[p2],res,8);    
}


// int getStrValueByp(char *X,char *Y,int p,unsigned char *blk)
// {
//     if (p>=56)
//     {
//         *X=NULL;
//         *Y=NULL;
//         return -1;
//     }
//     for (int i = 0; i < 4; i++)
//     {
//         X[i] = *(blk+p);
//         p++;
//     }
    
//     for (int i = 0; i < 4; i++)
//     {
//         Y[i] = *(blk+p);
//         p++;
//     }
// }